1. Field of the Invention
The present invention relates to error diffusion processing devices. More particularly, the present invention relates to an error diffusion processing device that uses a data driven type processing device to perform an operation for error diffusion.
2. Description of the Background Art
Error diffusion is a technique that is necessary when a printer or display device is so low in quantization level of an image, as in a facsimile device, that intermediate tones cannot be expressed when an image is taken in, processed and output with such a low quantization level unaltered. In other words, the technique is used when the quantization level of an output device like a display device or printer is lower than the quantization level when input from a reading device. More specifically, the technique is necessary in the case where, while the reading device has a multi-valued, e.g., 8-bit, analog to digital (A/D) converter, the display device is for binary display, so that the quantization level of the read image should be decreased accordingly.
When the quantization level is being decreased from the multi-valued level to the binary level, there is a possibility that the intermediate tones of the multi-valued images and hence continuity thereof will be lost. The error diffusion is the technique to express such continuity held by the multi-valued images in a pseudo manner. In other words, even if the quantization level of the output device is low, the technique enables the pseudo intermediate tones to be expressed, and thus, by increasing the quantization level of the reading device, it becomes possible to obtain a better image without altering the output device.
FIGS. 10A and 10B illustrate the error diffusion process. In FIGS. 10A and 10B, each rectangle represents a pixel, and a pixel being processed, or a target pixel, is marked with ⊚. It is assumed that the quantization is conducted from top to bottom in an image, and from left to right on a line. Shaded rectangles represent those for which the quantization has been completed. Comparing FIG. 10A with FIG. 10B, it is shown that the quantization has advanced one pixel to the right. The method of error diffusion illustrated herein is to distribute (or to diffuse) quantization error of the target pixel to its neighboring four pixels for which the quantization is not yet done, by multiplying the error by specific ratios of a, b, c and d, respectively. As shown in FIGS. 10A and 10B, the error of the pixel having undergone the quantization is successively distributed to the pixels having not yet undergone the quantization, so that the pixels should be processed one by one in order, with sequential processing. Thus, in the error diffusion, the sequential processing is required for each error, and real-time processing is necessary to complete the processing at a rate with which the images are being sent, and therefore, the sequential processing should be conducted at high speed. To solve these problems, several techniques as follows have conventionally been proposed.
The first example of such conventional techniques is a signal processing device disclosed in Japanese Patent Laying-Open No. 5-75863. This signal processing device includes means for binarizing adjacent pixels in parallel, means for generating the errors, and a filter for averaging the errors. It can downscale a buffer memory, and decrease the number of bits of the binarized errors, or store average values for a plurality of pixels. This technique is advantageous in that the memory region as well as the number of memory access times is reduced, allowing for speeding. The disadvantage is that the algorithm for error diffusing processing is specialized, so that it cannot be used when it does not agree with a required specification.
The second example of the conventional techniques is method and device for image processing disclosed in Japanese Patent Laying-Open No. 6-266324. In this example, binarization and error diffusion are performed for each scanning line, and the error data are stored in an error data storing memory for a next stage. Error diffusion instructions are then carried out in parallel for the respective scanning lines. The advantage of this technique is that computing units for error diffusion are provided in parallel, and paths for propagation of the error data among the computing units are also provided, so that parallelism is ensured to perform essentially parallel operations. This technique, however, exhibits a problem that, as it includes such parallel computing units for the error diffusion, the number of circuits is increased by α, corresponding to the number of such parallel computing units plus the one for coupling those parallel circuits.
The third example of the conventional techniques is method and device for block parallel error diffusion disclosed in Japanese Patent Laying-Open No. 6-301364. In this technique, an input image is divided into a plurality of blocks, and error diffusion is conducted for each block. Additional processing is conducted for the boundary of the blocks, so as to realize high-speed parallel processing. The advantage of this technique, as in the second example, is that parallel circuits are provided, and thus, it is possible to increase the operation speed in proportion to the circuit scale. This however poses a problem, again as in the second example, that the circuit scale will be increased proportional to the number of parallel elements.
The fourth example of the conventional techniques is method and device for parallel error diffusion disclosed in Japanese Patent Laying-Open No. 7-20839. In this example, a plurality of error diffusion circuits are provided so as to increase the entire speed without increasing the speed of the respective circuits. This technique again exhibits the same advantage and disadvantage as in the second and third examples.
The fifth example is an image processor disclosed in Japanese Patent Laying-Open No. 8-317211. In this example, image data of one raster is taken in and processed using a number of parallel computing units corresponding to one raster that can access data of neighboring four pixels. The computing units are not dedicated to the error diffusion, and therefore, it is unnecessary to add circuits for the processing. However, the circuit scale allowing the image of one raster to be taken in and to be processed in parallel becomes necessary.
The sixth example of the conventional techniques is a halftone processing method disclosed in Japanese Patent Laying-Open No. 10-334231. In this example, each pixel line is divided into a plurality of segments, and these multiple segments are processed in parallel for error diffusion, with a cut filter being used for a pixel immediately before the boundary of the segments and a normal filter for the other pixels. With this technique, it is possible to realize parallelism of the error diffusion within a pixel column without degrading the image quality. In other words, the error diffusion that should be conducted with sequential processing can be done with parallel processing. This however poses a problem, as in the other examples, that a series of pixels are divided into segments and processed segment by segment in parallel, so that the circuit scale is increased according to the number of parallel elements.
The seventh example is image processor and error diffusing processing method disclosed in Japanese Patent Laying-Open No. 11-146202. In this example, quantization error of a target pixel in a raster is obtained by predicting it from the quantization error in the preceding raster. Thus, in practice, it becomes unnecessary to wait for a processing result of the immediately preceding pixel to arrive before starting processing of the target pixel. Accordingly, using parallel processors, simultaneous processing of a plurality of pixels and also batch processing of all pixels within the same raster become possible.
These conventional techniques are classified into two groups: one for attempting speeding of processing by reducing the number of memory accesses as in the first and seventh examples; and the other for attempting speeding of processing by increasing the processing amounts between parallel processing as in the second through sixth examples.
In addition to the above-described techniques, a data driven type information processing device is proposed which performs parallel processing and thus has attracted attention as an image processing device for use in high-speed processing of a large amount of operations, e.g., for image processing. For such a data processing device performing the data driven type information processing operation, a data transmitting device employing non-synchronous handshake has been utilized. This sends/receives a data transfer request signal and a transfer permission signal indicating whether the data transfer is permitted, to effectually perform data transfer. The detail thereof is described in Japanese Patent Laying-Open No. 6-83731 by the applicant of the present invention.
A data driven type information processing device is provided with necessary circuits including computing units and memories, and the computing units are located within the information processing device. In the data driven type information processing device, as implied by the name, data drives each computing unit within the processing device, and each computing unit is allowed to start processing once data to be processed (to be operated) are ready therein.
In the data driven type information processing device, the data flows through respective computing units in the form of packets. Each packet consists of data and a portion called a tag containing data identification information. The operations are conducted according to the flow of these packets.
FIG. 11 shows a model of the computing unit in the data driven type information processing device. FIG. 12 shows a model of the packet.
As shown in FIG. 11, the computing unit 101 receives and processes data in the form of two packets, input packets 1 and 2, and outputs the result as an output packet. When data to be operated arrives at computing unit 101 as input packet 1, computing unit 101 holds the data included in input packet 1 and waits for arrival of its counterpart of operation. Upon arrival of input packet 2, when the two packets are recognized as the counterparts of operation, computing unit 101 starts processing. At this time, one packet can contain a plurality of pieces of data, as shown in FIG. 12, to realize parallelism.
Now, the packets will be described in brief with reference to FIG. 12. As explained above, each packet includes two major portions, a portion called a tag and the other containing data. The tag is described in Japanese Patent Laying-Open No. 6-83731, and thus, detailed description thereof will not be provided here. If a packet is considered literally as a parcel or a package, data is packed in the package and the package is sent with a tag or a shipping tag attached thereto. At this time, it will be efficient if more than one piece of data (four in FIG. 12) is contained in one packet. Specifically, overhead required for the operation, e.g., time necessary for packet transfer or delay due to a mechanism for identification of the packet, can be suppressed.
Thus, by increasing the number of pieces of data being contained in a packet, it becomes possible to perform a kind of parallel processing, thereby improving the processing efficiency when seen as the entire processing device. Even in the case of the data driven type, a plurality of computing units may be prepared within the information processing device, and processing can be performed independently from each other in the plurality of data driven type processors. As the plurality of computing units are provided, processing can be conducted sequentially using any idle computing unit, without waiting for completion of the preceding operation. This improves the processing efficiency.
The method for rapid and parallel processing being characteristic of the data driven type information processing device has been described. Instead, a method for speeding packet flow can of course be considered. One way to increase the speed of packet flow is to decrease operation time. This is accomplished not only by simply increasing the processing speed of circuits to reduce time required for operations, but also by decreasing time necessary for reading and writing of operation results.
In the error diffusion, sequential processing is conducted wherein one pixel is subjected to processing after the processing of the previous pixel is completed, and a large amount of processing is required for one pixel. With a method using a plurality of identical computing units, the circuit scale would be increased, and sending/receiving of error data between the computing units and their timings would become complex. Thus, it is considered that a method using packets each containing a plurality of pieces of data will be advantageous.
As described above, if a data driven type information processing device can be used for the error diffusion process, a processing device promising high-speed processing and advantageous in terms of circuit scale is expected.
However, if the conventional techniques described above as the first through seventh examples are applied to such a data driven type processing device, the following problems will arise.
First, the technique of the first example employs a specialized algorithm as described above, and is not for use in general purposes. It cannot be applied to a data driven type processing device.
Referring to the second, third and fourth examples, these processing methods employing computing circuits placed in parallel may be used for the data driven type. However, they cannot be applied to parallel processing of the type in which a plurality of pieces of data are processed packet by packet (i.e., parallel processing using packets each containing a plurality of pieces of data).
Referring to the fifth example, the computing unit is not dedicated to the error diffusion. If it is employed for the error diffusion, circuit scale large enough to take in image data for one raster will be necessary.
The technique of the sixth example is again the technique to process distant pixels in parallel, as in the other examples. It cannot be used for the parallel processing for use in the data driven type in which neighboring pixels are contained in one packet.
The technique of the seventh example is characterized by a computing device predicting error diffusion. Like the first example, it is not for use in general purposes, and cannot be applied to the data driven type processing device.
A data driven type processing device is capable of processing a plurality of pieces of data contained in one packet, so as to increase the execution speed. However, the error diffusion requires sequential processing, and the parallel processing is inappropriate therefor. The parallel processing described in the second through sixth examples above, except the fifth example, employs a plurality of error computing circuits to perform processing block by block. Such parallel processing cannot be applied to the parallel processing as in the data driven type that employs packets each containing a plurality of pieces of data.
The fifth example discloses the technique to take in all the pixel data for one raster and to use a plurality of computing units in parallel to increase the processing speed. Such a technique is inapplicable either, as it would simply increases the circuit scale.